1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.annotations.GwtIncompatible;
23
24 import java.io.IOException;
25 import java.io.ObjectInputStream;
26 import java.io.ObjectOutputStream;
27 import java.util.Collection;
28 import java.util.Comparator;
29 import java.util.NavigableMap;
30 import java.util.NavigableSet;
31 import java.util.SortedSet;
32 import java.util.TreeMap;
33 import java.util.TreeSet;
34
35 import javax.annotation.Nullable;
36
37 /**
38 * Implementation of {@code Multimap} whose keys and values are ordered by
39 * their natural ordering or by supplied comparators. In all cases, this
40 * implementation uses {@link Comparable#compareTo} or {@link
41 * Comparator#compare} instead of {@link Object#equals} to determine
42 * equivalence of instances.
43 *
44 * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent
45 * with equals</i> as explained by the {@link Comparable} class specification.
46 * Otherwise, the resulting multiset will violate the general contract of {@link
47 * SetMultimap}, which it is specified in terms of {@link Object#equals}.
48 *
49 * <p>The collections returned by {@code keySet} and {@code asMap} iterate
50 * through the keys according to the key comparator ordering or the natural
51 * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code
52 * replaceValues} return collections that iterate through the values according
53 * to the value comparator ordering or the natural ordering of the values. The
54 * collections generated by {@code entries}, {@code keys}, and {@code values}
55 * iterate across the keys according to the above key ordering, and for each
56 * key they iterate across the values according to the value ordering.
57 *
58 * <p>The multimap does not store duplicate key-value pairs. Adding a new
59 * key-value pair equal to an existing key-value pair has no effect.
60 *
61 * <p>Null keys and values are permitted (provided, of course, that the
62 * respective comparators support them). All optional multimap methods are
63 * supported, and all returned views are modifiable.
64 *
65 * <p>This class is not threadsafe when any concurrent operations update the
66 * multimap. Concurrent read operations will work correctly. To allow concurrent
67 * update operations, wrap your multimap with a call to {@link
68 * Multimaps#synchronizedSortedSetMultimap}.
69 *
70 * <p>See the Guava User Guide article on <a href=
71 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
72 * {@code Multimap}</a>.
73 *
74 * @author Jared Levy
75 * @author Louis Wasserman
76 * @since 2.0 (imported from Google Collections Library)
77 */
78 @GwtCompatible(serializable = true, emulated = true)
79 public class TreeMultimap<K, V> extends AbstractSortedKeySortedSetMultimap<K, V> {
80 private transient Comparator<? super K> keyComparator;
81 private transient Comparator<? super V> valueComparator;
82
83 /**
84 * Creates an empty {@code TreeMultimap} ordered by the natural ordering of
85 * its keys and values.
86 */
87 public static <K extends Comparable, V extends Comparable>
88 TreeMultimap<K, V> create() {
89 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural());
90 }
91
92 /**
93 * Creates an empty {@code TreeMultimap} instance using explicit comparators.
94 * Neither comparator may be null; use {@link Ordering#natural()} to specify
95 * natural order.
96 *
97 * @param keyComparator the comparator that determines the key ordering
98 * @param valueComparator the comparator that determines the value ordering
99 */
100 public static <K, V> TreeMultimap<K, V> create(
101 Comparator<? super K> keyComparator,
102 Comparator<? super V> valueComparator) {
103 return new TreeMultimap<K, V>(checkNotNull(keyComparator),
104 checkNotNull(valueComparator));
105 }
106
107 /**
108 * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its
109 * keys and values, with the same mappings as the specified multimap.
110 *
111 * @param multimap the multimap whose contents are copied to this multimap
112 */
113 public static <K extends Comparable, V extends Comparable>
114 TreeMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
115 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural(),
116 multimap);
117 }
118
119 TreeMultimap(Comparator<? super K> keyComparator,
120 Comparator<? super V> valueComparator) {
121 super(new TreeMap<K, Collection<V>>(keyComparator));
122 this.keyComparator = keyComparator;
123 this.valueComparator = valueComparator;
124 }
125
126 private TreeMultimap(Comparator<? super K> keyComparator,
127 Comparator<? super V> valueComparator,
128 Multimap<? extends K, ? extends V> multimap) {
129 this(keyComparator, valueComparator);
130 putAll(multimap);
131 }
132
133 /**
134 * {@inheritDoc}
135 *
136 * <p>Creates an empty {@code TreeSet} for a collection of values for one key.
137 *
138 * @return a new {@code TreeSet} containing a collection of values for one
139 * key
140 */
141 @Override SortedSet<V> createCollection() {
142 return new TreeSet<V>(valueComparator);
143 }
144
145 @Override
146 Collection<V> createCollection(@Nullable K key) {
147 if (key == null) {
148 keyComparator().compare(key, key);
149 }
150 return super.createCollection(key);
151 }
152
153 /**
154 * Returns the comparator that orders the multimap keys.
155 */
156 public Comparator<? super K> keyComparator() {
157 return keyComparator;
158 }
159
160 @Override
161 public Comparator<? super V> valueComparator() {
162 return valueComparator;
163 }
164
165 /*
166 * The following @GwtIncompatible methods override the methods in
167 * AbstractSortedKeySortedSetMultimap, so GWT will fall back to the ASKSSM implementations,
168 * which return SortedSets and SortedMaps.
169 */
170
171 @Override
172 @GwtIncompatible("NavigableMap")
173 NavigableMap<K, Collection<V>> backingMap() {
174 return (NavigableMap<K, Collection<V>>) super.backingMap();
175 }
176
177 /**
178 * @since 14.0 (present with return type {@code SortedSet} since 2.0)
179 */
180 @Override
181 @GwtIncompatible("NavigableSet")
182 public NavigableSet<V> get(@Nullable K key) {
183 return (NavigableSet<V>) super.get(key);
184 }
185
186 @Override
187 @GwtIncompatible("NavigableSet")
188 Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) {
189 return Sets.unmodifiableNavigableSet((NavigableSet<V>) collection);
190 }
191
192 @Override
193 @GwtIncompatible("NavigableSet")
194 Collection<V> wrapCollection(K key, Collection<V> collection) {
195 return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
196 }
197
198 /**
199 * {@inheritDoc}
200 *
201 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
202 * returns a {@link NavigableSet}, instead of the {@link java.util.Set} specified
203 * in the {@link Multimap} interface.
204 *
205 * @since 14.0 (present with return type {@code SortedSet} since 2.0)
206 */
207 @Override
208 @GwtIncompatible("NavigableSet")
209 public NavigableSet<K> keySet() {
210 return (NavigableSet<K>) super.keySet();
211 }
212
213 @Override
214 @GwtIncompatible("NavigableSet")
215 NavigableSet<K> createKeySet() {
216 return new NavigableKeySet(backingMap());
217 }
218
219 /**
220 * {@inheritDoc}
221 *
222 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
223 * returns a {@link NavigableMap}, instead of the {@link java.util.Map} specified
224 * in the {@link Multimap} interface.
225 *
226 * @since 14.0 (present with return type {@code SortedMap} since 2.0)
227 */
228 @Override
229 @GwtIncompatible("NavigableMap")
230 public NavigableMap<K, Collection<V>> asMap() {
231 return (NavigableMap<K, Collection<V>>) super.asMap();
232 }
233
234 @Override
235 @GwtIncompatible("NavigableMap")
236 NavigableMap<K, Collection<V>> createAsMap() {
237 return new NavigableAsMap(backingMap());
238 }
239
240 /**
241 * @serialData key comparator, value comparator, number of distinct keys, and
242 * then for each distinct key: the key, number of values for that key, and
243 * key values
244 */
245 @GwtIncompatible("java.io.ObjectOutputStream")
246 private void writeObject(ObjectOutputStream stream) throws IOException {
247 stream.defaultWriteObject();
248 stream.writeObject(keyComparator());
249 stream.writeObject(valueComparator());
250 Serialization.writeMultimap(this, stream);
251 }
252
253 @GwtIncompatible("java.io.ObjectInputStream")
254 @SuppressWarnings("unchecked") // reading data stored by writeObject
255 private void readObject(ObjectInputStream stream)
256 throws IOException, ClassNotFoundException {
257 stream.defaultReadObject();
258 keyComparator = checkNotNull((Comparator<? super K>) stream.readObject());
259 valueComparator = checkNotNull((Comparator<? super V>) stream.readObject());
260 setMap(new TreeMap<K, Collection<V>>(keyComparator));
261 Serialization.populateMultimap(this, stream);
262 }
263
264 @GwtIncompatible("not needed in emulated source")
265 private static final long serialVersionUID = 0;
266 }